\documentclass[UTF8]{ctexart}

\usepackage[a4paper, hmargin=1.25in, vmargin=1in]{geometry}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{textcomp}
\usepackage{multirow}
\usepackage{makecell}
\usepackage{setspace}
% \usepackage{listings}
% \usepackage{color}
% \usepackage{algorithm}
\usepackage[linesnumbered, boxed]{algorithm2e}
\usepackage{indentfirst}
\usepackage[tight,footnotesize]{subfigure}
\usepackage[raggedright]{titlesec}
% \usepackage[framed,numbered]{mcode}

\renewcommand{\algorithmcfname}{算法}
% \DeclareUnicodeCharacter{00A0}{ }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\title{Hadlock~最短路径算法在布线问题中的应用}
\author{王梦硕 （13110720021）}
\date{2016~年~6~月~25~日}
\maketitle

\begin{spacing}{1.5}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
本文档是对~VLSI~布图设计方法学课程的课程设计的说明文档。本次课程设计的内容是~Hadlock~最短路径布线算法。本文档简要介绍了~Hadlock~算法的研究背景和相关算法，详细介绍了Hadlock 算法的基本思想与实现，给出实验结果，并给出总结。
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{绪论}
\subsection{背景介绍}
布线是集成电路物理设计中的重要环节。布线的任务是根据给定网表，完成电路模块之间的互连。在布线问题中，最基本的问题是寻找两个模块之间的可能路径，并在此基础上最小化路径代价（cost）。这个问题可以被进一步抽象成在一个网格图（grid graph）中寻找从一个顶点到另一个顶点的最小代价路径，即单源最短路径问题（single source shortest paths problem）。通常这里的最短路径指的是最短曼哈顿距离。

\subsection{问题描述}
单源最短路径问题定义如下。给定带权图{ $G=(V,E)$ }及其权重函数{ $w:E\to{}\mathbb{R}$}。问题是：对一个单一起点{ $s\in{}V$}，确定其到途中其他顶点的路径的最小代价（cost）。对一条路径{ $\alpha=<u_0,u_1,...,u_k>$}，定义它的代价为{ $\alpha$ }中所有边的权重之和：
\begin{equation}
  c(\alpha)=\sum_{i=1}^{k}w\cdot(u_{i-1},u_i).
\end{equation}
在一个图中，从顶点{ $u$ }到顶点{ $v$ }的最短路径权重（shortest path weight）定义如下：
\begin{displaymath}
\delta(u,v) = \left\{ \begin{array}{ll}
 \mathrm{min}\{c(\alpha):u\xrightarrow{\alpha}v\} & \textrm{if there is a path from } u \textrm{ to } v, \\
 \infty & \textrm{otherwise.}
  \end{array} \right.
\end{displaymath}


因此，从顶点{ $u$ }到顶点{ $v$ }的最短路径是任何满足{ $c(\alpha)=\delta(u,v)$ }的路径{ $\alpha=<u,...,v>$}。

在下文的讨论中，为了简化问题，假设{ $G$ }中的所有边权重相等。这样，对一条路径{ $\alpha$}，它的代价即为它的长度：{$c(\alpha)=|\alpha|$}。


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{迷宫算法}
迷宫算法属于通用布线算法（general-purpose routing algorithms）的一种，可以应用在全局布线和细节布线中。迷宫算法最早由 Lee 在~\cite{lee1961an} 中提出（也称为 Lee 氏算法）是应用最广泛的寻找两点之间路径的算法。迷宫算法基于广度优先搜索（breadth-first-search, BFS）技术。

Lee 氏算法分为两步：填充（filling）和回溯（retracing）。填充步骤以一种波纹传播的方式进行。对寻找从{ $P$ }到{ $Q$ }的最短路径这一问题，从起点{ $P$ }开始，根据 “波阵面”（wavefront）与{ $P$ }的距离，逐步逐个地标记相邻的顶点，直到{ $Q$ }点被标记。一旦终点{ $Q$ }被标记，便可根据标记的降序，从{ $Q$ }回溯到{ $P$ }以找到最短路径。

Lee 氏算法分为两步：填充（filling）和回溯（retracing）。填充步骤以一种波纹传播（waveform propagation）的方式进行。对寻找从{ $P$ }到{ $Q$ }的最短路径这一问题，从起点{ $P$ }开始，根据 “波阵面”（wavefront）与{ $P$ }的距离，逐步逐个地标记相邻的顶点，直到{ $Q$ }点被标记。一旦终点{ $Q$ }被标记，便可根据标记的降序，从{ $Q$ }回溯到{ $P$ }以找到最短路径。

\begin{figure}[!htb]
  \label{lee}
  \begin{center}
    \includegraphics[width=5in]{doc_resource/waveform}
    \caption{Lee~氏算法用波纹传播方式填充网格图。}
  \end{center}
\end{figure}

\begin{figure}[!htb]
  \label{lee}
  \begin{center}
    \includegraphics[width=5in]{doc_resource/maze}
    \caption{Lee~氏算法的两个步骤：(a)~填充；(b)~回溯~\cite{Chen2009687}。}
  \end{center}
\end{figure}

Lee 氏算法的一个优良特性是：无论是否存在障碍，如果两个点之间存在路径，则它可以保证找到路径，并且该路径是最短的。但在实际应用中，Lee 氏算法速度较慢，并且消耗大量存储资源。它的时间和空间复杂度为{ $O(mn)$}，其中{ $m$ }和{ $n$ }分别为网格图纵向和横向的顶点数。因此，Lee 氏算法难以直接应用于大规模的密集设计~\cite{Chen2009687}。

为了降低 Lee 氏算法的运行时间和存储需求，学界提出了多种方法对 Lee 氏算法进行改良。这些改良算法主要在三个方面进行优化：1）编码方案，2）搜索算法；3）搜索空间。

\subsection{编码方案}
{Akers }在~\cite{akers1967modification}~提出：在回溯步骤中，对每一个标记，只要能区分它的前一个标记和后一个标记就足够了。基于这一观察，{Akers }提出了在填充步骤中使用{ 2-bit }编码方案。这种方案用序列{ 0,0,1,1,0,0,1,1,... }。这样，每一个标记的前一个标记和后一个标记都是不同的，回溯可以正确进行。另一个编码需要用来表示障碍，因此这种编码方案只需要{ 2-bit}。另一种较节省存储资源的方式由{ Hadlock }在~\cite{hadlock1977shortest}~中提出。它用绕行数（detour number）标记顶点，以减少搜索空间和运行时间。在第{ \ref{hadlock} }节，将详细介绍这一算法。

\subsection{搜索算法}
{Soukup }在~\cite{soukup1978fast}~中将深度优先搜索（depth-first-search, BFS）与广度有限搜索结合。从起点向终点进行深度一优先的线性搜索，直到遇到障碍或到达目标。当遇到障碍时，采用{ Lee }氏算法中的广度优先搜索绕过障碍。Soukup~算法的时间和空间复杂度与~Lee~氏算法一致，但一般而言速度比~Lee~氏算法快~10~到~50~倍。虽然~Soukup~算法可以找到两点之间的可能路径，但因为采用了深度优先算法，所以不能保证找到最优解。

\subsection{搜索空间}
一些技术可以通过减小搜索空间来减少迷宫算法的运行时间，如：起点选择（starting point selection）、双向扇出（double fanout）、加框（framing）等。
这些技术都可以明显地减少迷宫算法需要标记的顶点数量。起点选择技术选择最靠近芯片边界的断点作为起点。这样可以避免标记边界外的顶点，从而减少搜索空间。双向扇出从起点和终点同时开始波纹传播，减少需要标记的范围。加框技术将搜索限定在一个长方形区域中，例如，比起点与终点确定的方框大~10\%。如果目前搜索区域内无法找到可行解，则需要扩大搜索区域，并重新进行迷宫算法。显然，一旦采用加框技术，则~Lee~氏算法不再保证找到最短路径。



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A*~搜索}
\label{a-star}

虽然~Lee~氏算法能保证找到存在的最短路径，但由于它采用了广度优先算法，所以通常运行较慢。因为~Lee~氏算法的搜索过程中对搜索方向的选择没有优先顺序，因此它也被称为盲目搜索（blind search）。直觉上而言，可以通过减少对太可能出现在最终路径上的顶点的访问提高搜索算法的运行速度。

\cite{hart1968formal}~提出了一种通用的图搜索算法，即~A*~搜索。对一条路径~$\alpha$，A*~搜索用下式评估它的代价：
\begin{equation}
  f(\alpha) = g(\alpha) + h(\alpha).
\end{equation}
其中，$g(\alpha)$~是从起点到~$\alpha$~当前顶点的代价，$h(\alpha)$~是~$\alpha$~当前顶点到终点的估计（或预测）代价。在选择传播方向时，传播所得路径的代价越低，则选择该方向的优先级越高。因为~A*~搜索总是优先考虑最有可能通向终点的路径，因此又被称为最佳优先搜索（best-first search）。
广度优先搜索可以被认为是~A*~搜索的一个特例，对所有路径~$\alpha$~，有~$h(\alpha)=0$。

A*~搜索找到最优路径需要满足以下条件：对路径~$\alpha$，它的当前顶点到终点的估计代价不超过实际代价。因此，对于最短曼哈顿路径问题，$h(\alpha)=0$~可以被设为当前顶点到终点的曼哈顿距离。


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Hadlock 最短路径算法}
\label{hadlock}

Hadlock~最短路径算法（又称~Hadlock~最小绕行算法）由~Hadlock~在~\cite{hadlock1977shortest}中提出，用以解决网格图中的最短路径问题。Hadlock~算法结合了广度优先搜索和~A*~搜索~\cite{zheng1996finding}。通过引入绕行数（detour number）概念，Hadlock~算法改变了~Lee~氏算法的编码方式和搜索方式，减少了迷宫算法的存储消耗和运行时间。

\subsection{基本思想}
对于两个顶点{ $P$ }和{ $Q$}，用{ $d_M(P,Q)$ }表示两者之间的曼哈顿距离（Manhattan distance）。{$d_M(P,Q)$ }是{ $P$ }和{ $Q$ }两点间真实距离{ $d(P,Q)$ }的一个下界。假设以{ $P$ }作为起点，{$Q$ }作为终点，对于两者间路径中的一个顶点$u$而言，它的相邻顶点（以下简称邻点）可以分为两类。令{ $u$ }的邻点为{ $v$}，则对于{ $Q$ }而言：
如果{ $d_M(v,Q)+1=d_M(u,Q)$}，则{ $v$ }是{ $u$ }的{ $Q$}-正邻点（$Q$-positive neighbor）；如果{ $d_M(v,Q)-1=d_M(u,Q)$}，则{ $v$ }是{ $u$ }的{ $Q$}-负邻点（$Q$-negative neighbor）。
用{ $\alpha$ }表示从顶点{ $P$ }到顶点{ $x$ }的路径，{$\alpha$ }由{ $u_0=P,u_1,...,u_n=x$ }等顶点组成。该路径关于顶点{ $Q$ }的绕行数（detour number）{$d$ }等于这样的{ $u_i$ }的数量：{$u_i$ }是{ $u_{i-1}$ }的{ $Q$}-负邻点。因此，{$d$ }恰好就是该路径偏离{ $Q$ }的次数。
用{ $d_x$ }来表示从{ $P$ }到{ $Q$ }间最短路径的绕行数。

在所有从{ $P$ }到{ $Q$ }的路径中，可以按照路径长度对它们分类，这样分类的结果与按照绕行数分类的结果一致。以下定理给出了路径长度和绕行数之间的关系：

\textbf{定理 1：} 一条从{ $P$ }到{ $Q$ }的路径的长度为{ $d_M(P,Q)+2\cdot{}d$}，其中{ $d$ }是对于{ $Q$ }的绕行数。

根据定理{ 1}， 从{ $P$ }到{ $Q$ }的最短路径就是一条绕行数{ $d$ }最小的路径{ $\alpha$}，也就是说，可以通过尽量避免绕行来最小化路径长度。


\subsection{算法设计}
Hadlock 算法搜索从{ $P$ }到{ $Q$ }的最短路径{ $\alpha$}，并从 0 开始增大绕行数{ $d$}。在算法开始，所有顶点都是未访问的，一旦某个顶点被访问，就用当前的绕行数{ $d$ }将其标记。算法维护两个堆栈：{P-stack }和{ N-stack}。如不加说明，则{ $Q$}-正邻点的入栈和默认对象是{ P-stack}，{$Q$}-负邻点的入栈对应{ N-stack}。

~

\textbf{Hadlock最短路径算法：}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  $u:=P$，{$d:=0$}。
\item
  访问{ $u$}：用{ $d$ }标记{ $u$}。如果{ $u=Q$}，算法结束。将{ $u$ }的所有未标记{ $Q$}-负邻点入栈。如果{ $u$ }没有未标记的{ $Q$}-正邻点，执行步骤 3。令{ $u:=v$}，其中{ $v$ }是一个未标记的{ $Q$}-正邻点，将其他未标记的{ $Q$}-正零点入栈。重复执行步骤{ 2}。
\item
  如果{ P-stack }为空，执行步骤{ 4}。从{ P-stack }将{ $v$ }出栈。如果{ $v$ }已标记，则重复执行步骤{ 3}。令{ $u:=v$}，执行步骤{ 2}。
\item
  如果{ N-stack }为空，执行步骤{ 5}。互换{ P-stack }和{ N-stack}。令{ $d:=d+1$}。执行步骤{ 3}。
\item
  不存在从{ $P$ }到{ $Q$ }的路径。算法结束。
\end{enumerate}

显而易见，该算法可以找到最短的路径。该算法尽可能地向{ $Q$ }前进。在每一步，记录所有可选的顶点：用{ P-stack }记录靠近{ $Q$ }的顶点；用{ N-stack }记录远离{ $Q$ }的顶点。当前顶点可能是从上一个访问的顶点的{ $Q$}-正邻点（步骤{ 2}），或是当前通路（pass）访问过的某个顶点的{ $Q$}-正邻点， 或是上一个通路访问过的某个顶点的{ $Q$}-负邻点（步骤{ 3}）。当无法找到不增加绕行数{ $d$ }的邻点时，开始寻找绕行数为{ $d+1$ }的邻点（步骤{ 4}）。如果通过上述手段仍无法找到{ $Q$}，则停止算法（步骤{ 5}）。本课程设计中的~Hadlock~算法实现见附录·B中的算法~\ref{alg:hadlock_this}。
% 算法~\ref{alg:hadlock}~给出了~Hadlock~算法的一种实现。本课程设计采用的算法实现与算法~\ref{alg:hadlock}~不完全相同，详见附录·B~中的算法~\ref{alg:hadlock_this}。

%
% \begin{algorithm}[htb]
%   \caption{Hadlock~算法的一种实现~\cite{sherwani2012algorithms}}
%   \label{alg:hadlock}
%   \KwIn{the grid graph $M$, source vertex $P$, target vertex $Q$}
%   \KwOut{the shortest path $\alpha$}
%   $plist = P$\;
%   $nlist = \emptyset$\;
%   $detour = 0$\;
%   $path\_exists = \mathrm{FALSE}$\;
%   \While{$plist \ne \emptyset$}
%   {
%     \For{$u_i \in plist$}
%     {
%       \For{$u_j \in \mathrm{NEIGHBOR}(u_i)$}
%       {
%         \If{$M[u_j]=\mathrm{UNBLOCKED}$}
%         {
%           $D[u_j]=\mathrm{DETOUR\_NUMBER}(u_j)$\;
%           $\mathrm{INSERT}(u_j,nlist)$\;
%           \If{$u_j=Q$}
%           {
%             $path\_exists = \mathrm{TRUE}$\;
%             exist while\;
%           }
%         }
%       }
%     }
%     \If{$nlist = \emptyset$}
%     {
%       $path\_exists = \mathrm{FALSE}$\;
%       exit while\;
%     }
%     $detour = \mathrm{MINIMUM\_DETOUR}(nlist)$\;
%     \For{$u_k \in nlist$}
%     {
%       \If{$D[u_k]=detour$}
%       {
%         $\mathrm{INSERT}(u_k,plist)$\;
%       }
%     }
%     $\mathrm{DELETE}(nlist,plist)$\;
%   }
%   \If{$path\_exits=\mathrm{TRUE}$}
%   {
%     $\alpha = \mathrm{RETRACE}(D)$\;
%   }
%   \Else
%   {
%     path does not exist;
%   }
% \end{algorithm}



\subsection{实验结果}
图~\ref{fig:setting}~是为验证实现的~Hadlock~算法而设计的实验测例。图中，S~为起点，T~为终点，标记~-1~的位置为阻碍。

\begin{figure}[!htb]
  \label{fig:setting}
  \begin{center}
    \includegraphics[width=3in]{doc_resource/setting2}
    \caption{实验测例：起点为~S，终点为~T，阻碍由~-1~标出。}
  \end{center}
\end{figure}

图~\ref{fig:filling}~和图~\ref{fig:retrace}~分别显示了~Hadlock~算法在处理这一问题时的填充和回溯两个步骤：在图~\ref{fig:filling}~所示的填充过程中，从起点~S~开始，根据绕行数标记可通行区域。因为~S~没有可通行的~T-正邻点，所以绕行数跳过了~0，直接从~1~开始。之后，在绕行数为~3~时到达了目标点~T；在图~\ref{fig:retrace}~所示的回溯过程中，总是沿着当前位置的~S-正邻点前进，直到到达~S。


\begin{figure}[!htb]
  \label{fig:filling}
  \begin{center}
    \includegraphics[width=3in]{doc_resource/filling2}
    \caption{Hadlock~算法的填充步骤，自然数表示绕行数。}
  \end{center}
\end{figure}


\begin{figure}[!htb]
  \label{fig:retrace}
  \begin{center}
    \includegraphics[width=3in]{doc_resource/retrace2}
    \caption{Hadlock~算法的回溯步骤，-2~标出回溯得到的路径。}
  \end{center}
\end{figure}



\subsection{算法分析}
Hadlock~算法的目标是在减少搜索时间的同时保证找到两个顶点之间的最短路径。Hadlock~算法结合了广度优先搜索和~A*搜索思想，可以保证找到存在的一条最短路径。Hadlock~算法与~Lee~氏算法的主要区别在于编码方式。Hadlock~算法用绕行数标记波纹传播到的顶点。这种编码方式让~Hadlock~算法在一定程度上拥有了深度优先搜索的特质。例如，当起点与终点之间的理论最短曼哈顿路径未被阻挡时，绕行数为~0，Hadlock~算法完全不会访问最短路径以外的顶点，如图~\ref{fig:demo3}~所示。

\begin{figure}
\centering
\subfigure[填充]{
\label{fig:demo3_fill}
\includegraphics[width=2.5in]{doc_resource/filling3}}
\hspace{0.5in}
\subfigure[回溯]{
\label{fig:demo3_retrace}
\includegraphics[width=2.5in]{doc_resource/retrace3}}
\caption{绕行数为~0~的情况}
\label{fig:demo3}
\end{figure}

Hadlock~算法的继承了~Lee~氏算法的优点，即可以保证找到一条两点之间存在的最短路径。根据~\cite{hadlock1977shortest}~中的证明，Hadlock~算法的运算复杂度在~$O(n)$~到~$O(\sqrt{n})$~之间，其中~$n$~为网格图中的顶点数。


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{总结}

本文档着重叙述了~Hadlock~最短路径算法在布线问题中的应用。Hadlock~算法适用于网格图中的最短曼哈顿路径问题。在迷宫算法的基础上，Hadlock~算法采用~A*搜索思想，提出了基于绕行数的编码方案。Hadlock~算法在保证找到最优解的同时，提高了迷宫算法的效率。










%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{spacing}

\bibliographystyle{IEEEtran}
\bibliography{doc_resource/Hadlock}


\appendix
  \section{代码文件说明}
  考虑到~MATLAB~的开发速度以及对矩阵操作的先天优势，本课程设计的所有代码均用~MATLAB~实现。代码文件及相关说明如下：

  % \flushleft
  \begin{description}
    \item[hadlock.m] Hadlock~算法的~MATLAB~函数。
    \item[hadlock\_disp.m] 功能与~hadlock.m~类似，增加了显示功能。
    \item[hadlockretrace.m] 回溯函数。
    \item[neighbor.m] 返回某个顶点的~$Q$-正邻点和~$Q$-负邻点。
  \end{description}

  下面是每个函数的详细说明。

  \subsection{hadlock.m}
  调用方式：
  \begin{equation}
    \mathrm{[route, existflag] = hadlock(Maze, source, target)} \nonumber
  \end{equation}

  hadlock.m~文件是~Hadlock~算法的~MATLAB~函数。该函数接收~3~个输入，返回~2~个输出:

  % \flushleft
  \begin{description}
    \item[Maze] 输入：$m\times{}n$~的矩阵，用来描述布线中的可通行/不可通行区域。其中用~nan~标记所有可通行的顶点，用~-1~标记所有不可通行的顶点。
    \item[source] 输入：2~维向量，用来描述搜索的起点的坐标。
    \item[target] 输入：2~维向量，用来描述搜索的终点的坐标。
    \item[route] 输出：$k\times{}2$~的矩阵，表示输出的最短路径。每一行表示路径中一个顶点的坐标。$k$~为路径长度。如果没有可行路径，route~为空。
    \item[existflag] 输出：布尔变量，表示是否找到可行路径。如果存在，取值为~1，否则为~0。
  \end{description}

  \subsection{hadlock\_disp.m}
  调用方式：
  \begin{equation}
    \mathrm{[route, existflag, mov] = hadlock\_disp(Maze, start, target)} \nonumber
  \end{equation}

  功能与~hadlock.m~类似，区别在于会在运行过程中用图像显示算法运行过程。与~hadlock.m~相比，hadlock\_disp.m~多出一个输出：

  \begin{description}
    \item[mov] 输出：MATLAB~的帧向量，存储Hadlock~算法运行过程的视频。mov~每一个元素显示~Hadlock~算法的一个运行步骤。
  \end{description}

  \subsection{hadlockretrace.m}
  调用方式：
  \begin{equation}
    \mathrm{route = hadlockretrace(M,s,t,d)} \nonumber
  \end{equation}

  hadlockretrace.m~是~hadlock.m~和~hadlock\_disp.m~函数中调用的回溯函数，接收~4~个输入，返回主调函数中的~route~矩阵：

  \begin{description}
    \item[M] 输入：$m\times{}n$~的矩阵，用来描述布线中的可通行/不可通行区域。其中用~nan~标记所有可通行的顶点，用~-1~标记所有不可通行的顶点。
    \item[s] 输入：2~维向量，用来描述搜索的起点的坐标。
    \item[t] 输入：2~维向量，用来描述搜索的终点的坐标。
    \item[d] 输入：标量，填充步骤结束时的绕行数。
    \item[route] 输出：$k\times{}2$~的矩阵，表示输出的最短路径。每一行表示路径中一个顶点的坐标。$k$~为路径长度。
  \end{description}

  \subsection{neighbor.m}
  调用方式：
  \begin{equation}
    \mathrm{[Pos, Neg] = neighbor(Maze, target, now)} \nonumber
  \end{equation}

  neighbor.m~函数返回路径某个顶点相对于终点的所有未被访问的正邻点和负邻点，接收~3~个输入参数，返回两个输出：

  \begin{description}
    \item[Maze] 输入：$m\times{}n$~的矩阵，用来描述布线中的可通行/不可通行区域。其中用~nan~标记所有可通行的顶点，用~-1~标记所有不可通行的顶点。
    \item[target] 输入：2~维向量，用来描述搜索的终点的坐标。
    \item[now] 输入：2~维向量，用来描述目标顶点的坐标。
    \item[Pos] 输出：$k\times{}2$~的矩阵，表示~now~顶点相对于~target~的正邻点。每一行表示一个正邻点的坐标。k~为未被访问的正邻点的数量。
    \item[Neg] 输出：$k\times{}2$~的矩阵，表示~now~顶点相对于~target~的负邻点。每一行表示一个负邻点的坐标。k~为未被访问的负邻点的数量。
  \end{description}


  \section{本课程设计中的~Hadlock~算法实现}
  \begin{algorithm}[htb]
    \caption{本课程设计中的~Hadlock~算法实现}
    \label{alg:hadlock_this}
    \KwIn{the grid graph matrix $\mathbf{Maze}$, source vertex coordinate $\mathbf{source}$, target vertex coordinate $\mathbf{target}$}
    \KwOut{the shortest path $\mathbf{route}$, the exist flag $\mathbf{exist\_flag}$}
    $\mathbf{route} = []$\;
    $\mathbf{exist\_flag} = 1$\;
    $\mathbf{Pstack} = []$\;
    $\mathbf{Nstack} = []$\;
    $\mathbf{detour} = 0$\;
    $\mathbf{u} = \mathbf{source}$\;
    $\mathbf{Maze}[\mathbf{target}] = \mathbf{detour}$\;
    \While{$\mathbf{u} \ne \mathbf{target}$}
    {
      $[\mathbf{Pos}, \mathbf{Neg}] = \mathrm{NEIGHBOR}(\mathbf{Maze}, \mathbf{target}, \mathbf{u})$\;
      $\mathrm{stack}~\mathbf{Neg}~\mathrm{into}~\mathbf{Nstack}$\;
      \If{$\mathbf{Pos}~\mathrm{is~not~empty}$}
      {
        $\mathrm{\mathbf{v}} = \mathrm{POP}(\mathbf{Pos})$\;
        \If{$\mathbf{Maze}[\mathbf{v}]~\mathrm{is~labeled}$}
        {
          $\mathrm{CONTINUE}$\;
        }
        $ \mathbf{u} = \mathbf{v}$\;
        $\mathrm{stack~the~rest~of}~\mathbf{Pos}~\mathrm{into}~\mathbf{Pstack}$\;
      }
      \Else
      {
        \While{$\mathrm{true}$}
        {
          \If{$\mathbf{Pstack}~\mathrm{is~not~empty}$}
          {
            $\mathbf{v} =~\mathrm{POP}(\mathbf{Pstack})$\;
            \If{$\mathbf{Maze}[\mathbf{v}]~\mathrm{is~labeled}$}
            {
              $\mathrm{CONTINUE}$\;
            }
            $ \mathbf{u} = \mathbf{v}$\;
            $\mathrm{BREAK}$\;
          }
          \Else
          {
            \If{$\mathbf{Nstack}~\mathrm{is~empty}$}
            {
              $\mathbf{exist\_flag} = 0$\;
              $\mathrm{BREAK}$\;
            }
            $\mathbf{Pstack} = \mathbf{Nstack}$\;
            $\mathbf{Nstack} = []$\;
            $\mathbf{detour} = \mathbf{detour} + 1$\;
          }
        }
      }
      \If{$\mathbf{exist\_flag} = 0$}
      {
        $\mathrm{BREAK}$\;
      }
    }
    \If{$\mathbf{exist\_flag} = 1$}
    {
      $\mathbf{route} = \mathrm{RETRACE}(\mathbf{Maze},\mathbf{source},\mathbf{target},\mathbf{detour})$\;
    }
  \end{algorithm}


%   \section{Hadlock~算法的~MATLAB~实现}
%   \lstinputlisting{doc_resource/hadlock.m}


\end{document}
